1. Technical Field of the Invention
The present invention relates generally to the field of data communications error correction and, in particular, to a method and apparatus for decoding shortened cyclic codes using error trapping.
2. Description of Related Art
In a (wireless) communications system, control signaling information is encoded and transmitted using control channel messages.
One specific wireless standard specification in widespread use is the Global System Mobile (GSM) specification. GSM defines a number of control channel messages, including: FACCH, SACCH, SDCCH, AGCH, PCH, and BCCH. These 184-bit control channel messages are encoded with 40 parity check-bits, which are generated by a shortened binary cyclic block code belonging to, for example, the family of so-called Fire codes. These codes are defined in ETS 300909 (GSM 05.03 version 5.5.1): October 1998xe2x80x94using the generator polynomial:
G(X)=(X23+1)*(X17+X3+1).
The large number of parity check-bits virtually guarantees that a noise-corrupted signaling message will be detected and discarded by the base station.
The 40 parity check-bits generated by the Fire code can also be used to correct a single burst error up to 12 bits in length. Since signaling messages are interleaved over 4 or 8 bursts, the Fire code decoder could effectively correct error bursts of length 48 to 96 bits occurring in the air channel due to the diverse effects of signal interference. Since the 456 bits of a convolutionally encoded message are convolutionally decoded after deinterleaving and before the Fire code decoding procedure, a statistically significant percentage of signaling messages subject to error bursts can be completely recovered by the Fire code decoding procedure.
The error burst correction procedure is more than two orders of magnitude more computationally complex than the procedure for error detection. See (i) W. W. Peterson, Error-Correcting Codes, MIT Press, Cambridge, Mass, 1961 and (ii) R. T. Chien, xe2x80x9cBurst-Correction Codes with High-Speed Decoding,xe2x80x9d EEEE Transactions on Information Theory, IT(15), Issue 1, pp. 109-113, January 1969. Implementation of the Fire code decoder in real-time, therefore, has not been considered practical in consideration of other base transceiver stations (BTS) uplink burst processing requirements, such as demodulation, equalization, and convolutional error decoding.
The generator polynomial of a Fire code is expressed as the product of two polynomials G(x)=(x2txe2x88x921xe2x88x921)*p(x), where the polynomial p(x) is characterized by a periodicity factor r0. A code using G(x) is able to correct any single burst error less than or equal to xe2x80x98txe2x80x99 bits long.
Fire codes are represented by the notation F[n,k], where n is the number of coded bits, k is the length of the data to be coded, and (nxe2x88x92k) is the number of parity-check bits. The code can be shortened in length for a specific coding application by subtracting b bits from both the information word and its related code word to obtain the Fire Code F[N,K]=F[nxe2x88x92b,kxe2x88x92b].
In all of the following, for illustrative purposes, we shall refer to the case of the generator polynomial of the shortened Fire code F[224,184] specified in the aforementioned ETSI/GSM Standard, G(X)=(X23xe2x88x921)*(X17+X3+1), which can correct a single burst error up to t=12 bits long. The polynomial (X17+X3+1) has a periodicity factor r0=(217xe2x88x921)=131,071.
A cyclic code (e.g., Fire code) decoder error correction procedure is based on a fast error-trapping decoder for Fire codes first taught by Peterson and refined by Chien (see citations above). There, the error-trapping decoder includes two error syndrome shift registers: an error-pattern register and an error location register. The error-pattern register is based on the factor (X23+1) of the generator polynomial G(X)=(X23+1)*(X17+X3+1), and the error-location register is based on the factor (X17+X3+1).
In the Chien method, the data is first shifted into both registers. If an error is detected and determined to be correctable, the error correction procedure consists of the following steps:
1. Compute the number of xe2x80x980xe2x80x99 bits to be shifted into the first error syndrome register, the error-pattern register, until the burst error pattern is trapped in the xe2x80x98txe2x80x99 low order stages of this register. The number of required shifts is computed to be xcex1.
2. Compute the number of xe2x80x980xe2x80x99 bits to be shifted into the second error syndrome register, the error-location register, until the contents in the xe2x80x98txe2x80x99 low-order stages matches the burst error pattern trapped in step 1. The number of required shifts is computed to be xcex2.
3. Use xcex1 and xcex2 as inputs to a set of equations described in R. T. Chien, xe2x80x9cBurst-Correction Codes with High-Speed Decoding,xe2x80x9d IEEE Transactions on Information Theory, IT(15), Issue 1, pp. 109-113, January 1969 and U.S. Pat. No. 5,381,423 by E. Turco, Issued on Jan. 10, 1995 (xe2x80x9cTurcoxe2x80x9d) to compute the location of the burst error in the original data.
4. Use the error pattern trapped in step 1 to correct the burst error beginning at the location computed in step 3.
However, the Peterson and Chien fast trapping decoder does not explicitly address the requirements for dealing with a shortened Fire code. The GSM Fire code has been shortened to N=224 bits in length (i.e., K=184 bit control channel message plus 40 parity bits). The original length of the code corresponds to G(X)=(X23+1)*(X17+X3+1) is n=23*(217xe2x88x921)=3,014,633 bits. See S. Lin, D. J. Costello, Jr., Error Control Coding: Fundamentals and Applications, p. 261, Prentice-Hall Publishing, Englewood Cliffs, N.J., 1983. Thus, the code has been shortened by 3,014,633xe2x88x92224=3,014,409 bits. In order for a shortened cyclic code decoder""s syndrome registers to be properly initialized, in addition to shifting-in the data and parity bits, it is also necessary to shift in an additional number of xe2x80x980xe2x80x99 bits equal to the number of shortened bits. This would require an additional 3,014,409 xe2x80x980xe2x80x99 bits to be shifted into the syndrome registers.
Turco addresses the issue of shifting in the large number of xe2x80x980xe2x80x99 bits by teaching that it is not necessary to shift the shortened zero (xe2x80x980xe2x80x99) bits into both the error-location and error-pattern registers. Instead, the shortened zero bits are only shifted into the error-location register. The number of zero bits to be shifted is equal to (r0xe2x88x92N+1)=130,848 bits.
Once the error burst pattern and location have been identified, Peterson, Chien, and Turco solve a set of equations, as described above in step 3, to locate where the error burst resides in the original data.
In the present invention, it is not necessary to perform step 3 in the error correction procedure proposed by (i) W. W. Peterson, Error-Correcting Codes, MIT Press, Cambridge, Mass., 1961 and (ii) R. T. Chien, xe2x80x9cBurst-Correction Codes with High-Speed Decoding,xe2x80x9d WEEE Transactions on Information Theory, IT(15), Issue 1, pp. 109-113, January 1969 and described by Turco in U.S. Pat. No. 5,381,423, issued Jan. 10, 1995. Nor is it necessary to use the value corresponding to xcex1 in the Chien method to compute the location of the error burst. Rather, in the present invention, the location of the error burst is computed directly from the value xcex, which corresponds to the value xcex2 in step 2 of the Chien procedure.
According to the principles of the present invention, a method and apparatus are used for correcting error bursts in a communication system using shortened cyclic codes, such as shortened Fire codes. Data is loaded into a first error syndrome register and a second error syndrome register. The data in the registers may be evaluated to determine if the data bits contain a correctable error. Shortened zero bits are shifted into the second error syndrome register. A number of zero bits are shifted into the first error syndrome register to trap an error burst pattern in the data. A determination is made as to the number of zero bit shifts, xcex, into the second error syndrome register to trap the error burst location in the data. Using the value (xcexxe2x88x92c), where xe2x80x98cxe2x80x99 is a constant, and the error burst pattern, the error in the data is located and corrected.
The first error syndrome register may be referred to as an error pattern register, and the second error syndrome register may be referred to as an error location register. The number of shortened zero bits shifted into the second error syndrome register is (r0xe2x88x92N+1), which is based upon (i) the periodicity r0 of the smaller factor composing the cyclic code corresponding to the error location register and (ii) the length N of the shortened cyclic code. Typically, trapping the error burst pattern uses no more than (2txe2x88x922) shifts. Also, trapping the error burst location uses no more than (N+c) shift and compare operations. For TDMA-based GSM systems, the trappings require no more than 22 shifts and 237 shift and compare operations, respectively.
A signal processor may be employed to execute software implementing the decoder. Shifting the shortened zero bits and the other zero bits may be implemented in a manner that exploits the architecture of the signal processor. For example, logical operations AND, XOR and SHIFT, and arithmetic operation, MULTIPLY, may be combined to take advantage of the efficient pipeline process provided by the signal processor. In such an embodiment, a shift operation is executed in a single signal processor instruction cycle.
A system employing the cyclic code decoder may be used in a TDMA-based GSM system. In the case of using a signal processor to implement the processes described herein, the signal processor resources available during inactive time slots of the TDMA-based GSM system are utilized in a background mode to process the shifting-in of the shortened data zeros. In one embodiment, processing is distributed over a variable number of inactive radio channel time slots in order to provide enough signal processor resources to correct a frame of data while minimizing frame-buffering delays.
In a system employing the teachings described herein, error bursts are capable of being detected and corrected in real-time.